class Solution {
    #define maxn 50010
    #define ull unsigned long long
    #define B 271
    ull power[maxn];
    ull hashs[2][maxn];
    void init(int idx,string s)
    {
        power[0]=1;
        hashs[idx][0]=s[0];
        for(int i=1;i<s.size();i++)
        {
            hashs[idx][i]=hashs[idx][i-1]*B+s[i];
            power[i]=power[i-1]*B;
        }
    }
    ull get(int idx,int l,int r)
    {
        if(l==0)
            return hashs[idx][r];
        return hashs[idx][r]-hashs[idx][l-1]*power[r-l+1];
    }
public:
    string shortestPalindrome(string s) {
        init(0,s);
        reverse(s.begin(),s.end());//为了计算后缀
        init(1,s);
        reverse(s.begin(),s.end());
        int i,j;
        int n=s.size();
        for(i=n;i>=1;i--)
        {
            if(get(0,0,i-1) == get(1,n-i,n-1))//找前缀和后缀相同的最大哈希值
                break;
        }
        string ans;
        for(j=n-1;j>=i;j--)//输入前后相同的最短前缀串,从后面遍历时因为题目说可以在字符串前面添加字符
        {
            ans+=s[j];
        }
        ans+=s;
        return ans;
    }
};